1. Field of the Invention
The invention relates generally to methods and apparatus for synchronizing data transmission in computer networks and, in particular embodiments, to methods and apparatuses for synchronizing upstream network transmission in cable modems.
2. Description of Related Art
Data networks have different forms to serve different purposes. An example of a simple network is a network in an office that allows several computers to use one printer. Such a network is commonly known as a Local Area Network (LAN). Other networks may be more complex. The Internet is an example of a more complex network, in which many smaller networks from all over the world may be interconnected. The Internet allows worldwide transmission of many types of data, including text files, graphics, audio, and video data. A network that extends over a large geographical area is commonly known as a Wide Area Network (WAN).
WANs have commonly used the telephone system to transmit data over long distances. The telephone system is a convenient data transmission media because it has an established infrastructure which can reliably transmit data worldwide. A major drawback to data transmission via the telephone network, however, is the limited rate at which it can transmit data (its low bandwidth).
For users requiring higher bandwidth, sophisticated but expensive WAN systems have been built. For example, large businesses have utilized satellites orbiting the earth and microwave linked ground stations for the transmission of data. For the general user, however, the telephone system remains a prevalent choice as an acceptable tradeoff of cost and performance. In other words, the general user has accepted low bandwidth because the cost of obtaining greater bandwidth has been high.
Recently, cable television networks have become available. A typical cable TV system can carry many television stations, which are the equivalent of a large amount of data (high bandwidth), simultaneously. Because of the increasing availability of cable television infrastructure, using television cables as the medium for computer data networks has the potential for giving users high bandwidth at a reasonable cost. A cable TV system, however, requires several enhancements in order to function as a data network.
In its classic form, a cable TV system carries information in only one direction, from the cable system head end, to the individual user. The user""s interface to the system generally comprises a receiver, for example, a television or a stereo. The head end transmits television or stereo channels simultaneously. In general the user has no influence on what is transmitted and can only choose among the channels the head end is transmitting.
In contrast, a data network must carry data from the head end to the user (the downstream path) and from the user to the head end (the upstream path). The individual user requires equipment, such as a cable modem, that can both receive from the head end and transmit to it. A cable data network must be able to handle many individual users simultaneously, each of whom have control over what they receive and transmit.
In order for a cable TV network to operate as a data network, it requires a head end capable of both transmitting and receiving data as well as a user end equipped with the capability of both receiving and transmitting data through the use of equipment such as a Cable Modem (CM). To assure that each user receives the data they require, a network protocol must be implemented to allow independent users of the network to utilize the shared head end and the distribution network without interference from or receiving the data of other users.
The network protocol places requirements on both the head end and the user end. Generally, the head end serves as the network controller, and the user""s cable modem must be able to respond to commands from the head end. In order to support a number of independent users, the network protocol divides the system""s resources using two basic methods.
In a cable TV system the head end can transmit several TV channels simultaneously by placing them in different channels in the radio frequency (RF) spectrum. Similarly the network protocol divides the cable network""s bandwidth into frequency channels. Each user""s cable modem then can be tuned to receive and transmit on one or more of the channels. Generally, in a cable data network, the downstream transmissions are segregated from upstream transmissions by placing them on different RF channels. Such a method is termed Frequency Division Multiple Access (FDMA).
In order to accommodate a number of users, RF channels can be further divided into time slots and each user allotted a timeslot to transmit and receive. This method is commonly known as Time Division Multiple Access (TDMA).
The time slots for the downstream messages are determined by the head end network controller. The reception of data by users is determined by an addressing scheme. The head end transmits a unique address for each cable modem along with the data for that user; the individual modem is configured to accept only the data intended for it.
Allocating time slots for upstream messages generated by users is complicated by the fact that the upstream messages are initiated by independent units. In general, two types of schemes have been developed to control transmissions by the users: arbitration methods and allocation by the controller.
In a common arbitration system, the user""s modem initiates transmissions. The system includes a method for detecting collisions between user messages; i.e., more than one user attempting to transmit an upstream message at the same time. When a collision is detected the users must then retransmit their messages, usually adjusting the times at which they retransmit in a attempt to reduce the chances of another collision with messages from the same unit. This method has a drawback in that bandwidth is wasted when the messages that collided are retransmitted. As the channel becomes more crowded, the number of collisions tend to increase.
A method of utilization of the channel is to have the system controller assign a time interval for each user""s modem transmission. To implement such a method, the user""s transmission must be synchronized so as not to collide with each other. A common way to provide synchronization is to assign transmission time slots to each user. Each user can then transmit in a time assigned to them and collisions are avoided. The more precisely the user modems transmit at their assigned time, the more closely spaced the controller can schedule messages, and the greater the capacity of the network. Therefore, precise scheduling of user modem transmissions is desirable.
Precise synchronization between elements widely separated in space is not a trivial matter. Compensation for the skewing caused by the finite time required for the signals to travel time between elements must be added if correct synchronization is to be achieved. In addition, transmission of data over a cable may be accomplished by several different standards. One such standard is the MCNS or Multimedia Cable Network System standard, which has been promulgated primarily in North America by DOCSIS (the Data Over Cable System Interface Specification) which has become a de facto standard for compatible cable modems in North America. Multiple other standards have been promulgated; for example, the Digital Video Broadcasting (DVB) standard which is the standard produced by the European Broadcast Union (EBU) under the auspices of the European Telecommunications Standards Institute (ETSI). A system similar to the DVB system has also been proposed by DAVIC (Digital Audio Video Council). To address the synchronization problem MCNS systems may be implemented with a local clock in each Cable Modem, which periodically needs to be synchronized to a master clock within the cable system head end. DVB systems synchronize the local clock in the NIU (DVB terminology for Cable Modem) to the start of transmit marker which comprises a 3 millisecond upstream transmission period, instead of to a master clock. The synchronization of cable modems for the purpose of data transmission has two aspects: an initial offset by which the master clock in the cable system head end and the local time clock in each element (e.g. CM or NIU) differ and the rate at which the two clocks increment time. Typically the clock at the head end of a cable system is highly accurate, while the local clocks within each remote element are somewhat less accurate.
To control the transmission of messages MCNS systems generally synchronize local clocks in the user modem to a system time kept by a master clock within the Cable Modem Termination System (CMTS) at the head end. The CMTS can then command a user""s modem to transmit at a time measured by the system time. Synchronization of clocks in the user modems can be accomplished in two stages. First, during user modem initialization, the delays between transmission of a message by the user modem and its reception at the head end are measured and this measurement is transmitted to the user modem and stored in the user modem. This is typically referred to as the Ranging Process. Second, at irregular intervals, the head end transmits synchronization messages to the user modems. This may be referred to as the Update Process. The synchronization messages contain the value of the system time at which the message was sent. The user""s modem must accurately measure the times these messages arrive and use that information to synchronize their local clocks to the system time. Because the rate at which the local clock and master clock increment time may differ, even a perfect synchronization cannot be maintained over time and periodic adjustments are necessary.
In the DVB system the Ranging Process stage described above is similar to the MCNS but the Update Process is somewhat different. The terminology within the DVB system is also different than the MCNS system. The CMTS is referred to as the INA or Interactive Network Adapter. The cable modem from the MCNS system is referred to as the NIU or network interface unit in the DVB system. While the functions of these differently named components are similar, the methodology for cable modem transmission and reception is somewhat different. In the DVB system there are two recommended methods for transmitting downstream data and signals as opposed to the single method within the MCNS system. The two different methods of transmitting data and signals in a DVB system are referred to as the IB or In Band method and the OOB or Out of Band method. In the Out of Band case, synchronization information and 1-millisecond and 3-millisecond periods are derived from the time when specified bits of the bitstream are transmitted by the INA. The In Band case is similar to the MCNS system, but the synchronization message does not contain the value of the system time. Instead it points to the boundary of a 3 millisecond period, and will be primarily dealt with as an implementation which may contain embodiments of the invention. This will not preclude embodiments of the invention from being used in the OOB case, it merely means that the In Band case is more complex and more illustrative of aspects of the invention. Many other embodiments in various systems are possible and the MCNS and DVB examples included here are chosen as those most likely to be familiar to those skilled in the art and hence the most illustrative. In the DVB In Band case, a Media Access Control or MAC control message is transmitted to the NIU. Within the MAC control message (if it is designated as an active SYNC message) is a 10 bit upstream slot position register (USPR) that is increased by the INA every 3-millisecond period and a 16-bit upstream slot marker pointer. The upstream slot marker pointer contains a value representing a number of symbols. For convenience we shall refer to this number of symbols as UMV (or Upstream Marker Value). A symbol is a discrete piece of transmitted data. Symbols may comprise one, two, three, four or more bits each depending on what kind of modulation scheme is used to transmit the symbol. The UMV designates the number of symbols which must be counted from the beginning of the next MPEG-2 frame to the start of a three millisecond period. The NIU detects the next MPEG-2 frame after the MAC message by looking for the start of MPEG-2 header which is a hexadecimal value of 47. The NIU then counts UMV number of symbols. When UMV symbols have been counted, the beginning of the 3-millisecond period commences. The 3 millisecond periods are further divided into upstream transmission slots and free intervals. Other information within the MAC control message identifies specific slots that have been allotted to the particular NIU for upstream transmission. It is this timing information that may be used by the INA to synchronize its message upstream. In the DVB case, initializations and periodic adjustments, similar to those needed in the MCNS case, are necessary.
Thus there is a need in the art for cable modems that can synchronize and efficiently adjust their upstream transmission timing in order to accurately schedule upstream burst transmissions.
To overcome the limitations in the prior art described above, the specification discloses a system and method for synchronizing network transmissions, such as cable network transmissions, in remotely located units. Embodiments of the present invention may synchronize local clocks to a system time kept by a master clock in a cable network system, or may synchronize local clocks to transmission times. Embodiments of the present invention can be implemented in a computer under program control to minimize hardware complexity and to provide flexibility for system changes.
MCNS Version
In preferred exemplary MCNS embodiments, the system includes in each user modem: a local clock, a message receiver to store messages in memory, a time tag generator to insert into memory the value of the local clock when each message arrives, a computer capable of accessing the memory, and a computer program to extract the transmitted system time from selected messages and to calculate and synchronize the local clock to the transmitted system time. Preferred embodiments utilize a local clock, within the cable modem, implemented in hardware as a source of local timing and flexible firmware to both extract the system time transmitted from the head end from selected messages, to implement a Software Phase Locked Loop (SPLL) that synchronizes the local clock to the system time received from the CMTS, and to control the transmission of upstream messages.
DVB Version
A second preferred embodiment of the invention for DVB systems includes the same hardware elements as a preferred MCNS embodiment. The computer program in the DVB embodiment is changed, however, to account for the difference in synchronizing data. In the DVB embodiment, there is synchronizing information in an MPEG-2 Transport Stream (TS) packet or frame known as a MAC control message. Synchronization information within certain enabled MAC control messages frames points to a beginning of a 3-millisecond period. The 3-millisecond period is a time period when an upstream transmission period is to begin.
A SPLL similar to that found in the MCNS embodiment will be used to lock to the beginning of the upstream 3 millisecond period, so that the beginning of the transmit period, in terms of local time, may be found.
These and other objects, features, and advantages of embodiments of the invention will be apparent to those skilled in the art from the following detailed description of embodiments of the invention, when read with the drawings and appended claims.